/*
 * @lc app=leetcode.cn id=130 lang=cpp
 *
 * [130] 被围绕的区域
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    void dfs(const vector<vector<char>> &board, vector<vector<char>> &ans, int row, int column)
    {
        if (row >= 0 && row < ans.size() && column >= 0 && column < ans[0].size())
        {
            if (board[row][column] == 'O' && ans[row][column] != 'O')
            {
                ans[row][column] = 'O';
                dfs(board, ans, row + 1, column);
                dfs(board, ans, row - 1, column);
                dfs(board, ans, row, column - 1);
                dfs(board, ans, row, column + 1);
            }
        }
    }
    void solve(vector<vector<char>> &board)
    {
        const int m = board.size();
        const int n = board[0].size();
        vector<vector<char>> ans(m, vector<char>(n, 'X'));

        for (int i = 0; i < n; i++)
        {
            if (board[0][i] == 'O' && ans[0][i] != 'O')
            {
                dfs(board, ans, 0, i);
            }
            if (board[m - 1][i] == 'O' && ans[m - 1][i] != 'O')
            {
                dfs(board, ans, m - 1, i);
            }
        }

        for (int i = 0; i < m; i++)
        {
            if (board[i][0] == 'O' && ans[i][0] != 'O')
            {
                dfs(board, ans, i, 0);
            }
            if (board[i][n - 1] == 'O' && ans[i][n - 1] != 'O')
            {
                dfs(board, ans, i, n - 1);
            }
        }

        board.swap(ans);
    }
};

// @lc code=end
